package net.tp.algo.sort;

import net.tp.struct.adt.SinglyNode;

import java.util.Comparator;

/**
 *
 * Merge Sort for Singly Linked List.
 * <p>
 * Unlike merge sort for array, merge sort for singly linked list is a stable, in-place sort that runs in $O(n \log n)$ time. It rearranges the links among the node, therefore there is no need to copy elements to a temporary location.
 *
 * @author Trung Phan
 * @time $O(n \log n)$
 * @space $O(1)$
 *
 */
public class ListMergeSort {

    public static <E> SinglyNode<E> sort(SinglyNode<E> list, Comparator<? super E> comparator) {
        return sort(list, tail(list), comparator);
    }

    private static <E> SinglyNode<E> sort(SinglyNode<E> lo, SinglyNode<E> hi, Comparator<? super E> comparator) {
        assert hi.next == null;
        if (lo == hi) return lo;

        SinglyNode<E> mid1 = mid(lo, hi);
        SinglyNode<E> mid2 = mid1.next;
        mid1.next = null;

        SinglyNode<E> list1 = sort(lo, mid1, comparator);
        SinglyNode<E> list2 = sort(mid2, hi, comparator);

        return merge(list1, list2, comparator);

    }

    private static <E> SinglyNode<E> merge(SinglyNode<E> list1, SinglyNode<E> list2, Comparator<? super E> comparator) {
        SinglyNode<E> result = new SinglyNode<>(null, null);
        SinglyNode<E> tail = result;
        while (list1 != null && list2 != null) {
            if (comparator.compare(list1.element, list2.element) <= 0) {
                tail = tail.next = list1;
                list1 = list1.next;
            }
            else {
                tail = tail.next = list2;
                list2 = list2.next;
            }
            tail.next = null;
        }
        tail.next = (list1 != null ? list1 : list2);
        return result.next;
    }

    private static <E> SinglyNode<E> mid(SinglyNode<E> lo, SinglyNode<E> hi) {
        SinglyNode<E> mid = lo;
        for (SinglyNode<E> i = lo; i != null && i.next != null && i != hi && i.next != hi; i = i.next.next) {
            mid = mid.next;
        }
        return mid;
    }

    private static <E> SinglyNode<E> tail(SinglyNode<E> list) {
        if (list == null) return null;
        SinglyNode<E> tail = list;
        for (; tail.next != null; tail = tail.next);
        return tail;
    }

}
